public class Solution {
    /**
     * 最长公共前缀
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length <= 1) {
            return strs[0];
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for(int j = 0; j < strs.length; j++) {
                if (strs[j].length() <= i || strs[j].charAt(i) != ch) {
                    return sb.toString();
                }
            }
            sb.append(ch);
        }
        return sb.toString();
    }

    /**
     * 最长回文子串
     * 动态规划
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        // 动态规划
        int len = s.length();
        // 创建 dp 表
        boolean[][] dp = new boolean[len + 1][len + 1];
        s = " " + s;
        // 初始化
        for(int i = 0; i < len; i++) {
            dp[i][0] = true;
            dp[0][i] = true;
        }
        int begin = 0, count = 0;
        // 填表
        for(int i = len; i >= 1; i--) {
            for(int j = i; j <= len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > count) {
                    begin = i;
                    count = j - i + 1;
                }
            }
        }
        return s.substring(begin, begin + count);
    }

    /**
     * 最长回文子串
     * 中心扩展算法
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        // 中心扩展算法
        int begin = 0, count = 0;
        int len = s.length();
        for(int i = 0; i < len; i++) {
            // 扩展奇数长度字符串
            int left = i, right = i;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > count) {
                begin = left + 1;
                count = right - left - 1;
            }
            // 扩展偶数长度字符串
            left = i;
            right = i + 1;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > count) {
                begin = left + 1;
                count = right - left - 1;
            }
        }
        return s.substring(begin, begin + count);
    }

    /**
     * 二进制求和
     * @param aStr
     * @param bStr
     * @return
     */
    public String addBinary(String aStr, String bStr) {
        // 模拟加法计算过程
        StringBuilder sa = new StringBuilder(aStr).reverse();
        StringBuilder sb = new StringBuilder(bStr).reverse();
        StringBuilder res = new StringBuilder();
        int carry = 0, i = 0, j = 0;
        while (i < sa.length() && j < sb.length()) {
            int a = sa.charAt(i) - '0';
            int b = sb.charAt(j) - '0';
            res.append((char)((a + b + carry) % 2 + '0'));
            carry = (a + b + carry) / 2;
            i++;
            j++;
        }
        while (i < sa.length()) {
            int a = sa.charAt(i) - '0';
            res.append((char)((a + carry) % 2 + '0'));
            carry = (a + carry) / 2;
            i++;
        }
        while (j < sb.length()) {
            int b = sb.charAt(j) - '0';
            res.append((char)((b + carry) % 2 + '0'));
            carry = (b + carry) / 2;
            j++;
        }
        if (carry == 1) {
            res.append((char) (carry + '0'));
        }
        return res.reverse().toString();
    }

    /**
     * 字符串相乘
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {
        // 模拟相乘过程
        int len1 = num1.length();
        int len2 = num2.length();
        StringBuilder n1 = new StringBuilder(num1).reverse();
        StringBuilder n2 = new StringBuilder(num2).reverse();
        int[] tmp = new int[len1 + len2 - 1];
        // 无进位相乘并相加
        for(int i = 0; i < n1.length(); i++) {
            for (int j = 0; j < n2.length(); j++) {
                tmp[i + j] += ((n1.charAt(i) - '0') *(n2.charAt(j) - '0'));
            }
        }
        // 处理进位
        int cur = 0, t = 0;
        StringBuilder ret = new StringBuilder();
        while (cur < len2 + len1 - 1 || t != 0) {
            if (cur < len1 + len2 - 1) {
                t += tmp[cur++];
            }
            ret.append((char) (t % 10 + '0'));
            t /= 10;
        }
        // 删除多余的 0
        while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt(ret.length() - 1);
        }
        return ret.reverse().toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.multiply("9", "99");
    }
}
